﻿using System;
using System.Collections;

namespace BloomFilterTest
{
    class BloomFilter
    {
        private BitArray hashbits;
        private int numKeys;
        private int[] hashKeys;

        /// <summary>
        /// Creates a Bloom filter with specified m and k values.
        /// </summary>
        /// <param name="tableSize">Number of bits in hash table - m</param>
        /// <param name="nKeys">Number of Hash Keys - k</param>
        public BloomFilter(int tableSize, int nKeys)
        {
            numKeys = nKeys;
            hashKeys = new int[numKeys];
            hashbits = new BitArray(tableSize);
        }

        private int HashString(string s)
        {
            int hash = 0;

            for (int i = 0; i < s.Length; i++)
            {
                hash += s[i];
                hash += (hash << 10);
                hash ^= (hash >> 6);
            }
            hash += (hash << 3);
            hash ^= (hash >> 11);
            hash += (hash << 15);
            return hash;
        }

        private void CreateHashes(string str)
        {
            int hash1 = str.GetHashCode();
            int hash2 = HashString(str);

            // Performs Dillinger and Manolios double hashing. 
            for (int i = 0; i < numKeys; i++)
            {
                hashKeys[i] = Math.Abs((hash1 + (i * hash2)) % hashbits.Count);
            }
        }

        public bool Add(string str)
        {
            // Initially assume that the item is in the table
            bool collision = true;
            CreateHashes(str);
            foreach (int hash in hashKeys)
            {
                if (!hashbits[hash])
                {
                    // One of the bits wasn't set, so show that
                    // the item wasn't in the table, and set that bit.
                    collision = false;
                    hashbits[hash] = true;
                }
            }
            return collision;
        }

        public bool Contains(string item)
        {
            int hash1 = item.GetHashCode();
            int hash2 = HashString(item);
            for (int i = 0; i < numKeys; i++)
            {
                int temp = Math.Abs((hash1 + (i * hash2)) % hashbits.Count);
                if (hashbits[temp] == false)
                    return false;
            }
            return true;
        }
    }
}
